package main

import (
	"fmt"
)

/*
二分查找的思路: 要查找的数是 findVal
1 arr是一个有序数组，并且是从小到大排序。
2 先找到 中间的下标 middle = (leftIndex + rightIndex) / 2, 然后让中间下标的值和findVal进行比较。
2.1 如果 arr[middle] > findVal ,  就应该在  leftIndex — (middle - 1) 这个范围查找
2.2 如果 arr[middle] < findVal ,  就应该在  middel+1—rightIndex 这个范围查找
2.3 如果 arr[middle] == findVal, 找到
2.4 上面的2.1 2.2 2.3 的逻辑会递归执行
3 退出递归的条件
if  leftIndex > rightIndex {
   // 找不到..
   return ..
}
*/
// 二分查找的函数
func BinaryFind(arr *[6]int, leftIndex int, rightIndex int, findVal int) {
	// 判断leftIndex 是否大于 rightIndex
	if leftIndex > rightIndex {
		fmt.Println("找不到")
		return
	}

	// 先找中间的下标
	middle := (leftIndex + rightIndex) / 2
	if (*arr)[middle] > findVal {
		// 说明查找的数在  leftIndex - middel-1 这个范围
		BinaryFind(arr, leftIndex, middle-1, findVal)
	} else if (*arr)[middle] < findVal {
		// 说明查找的数在  middel+1 - rightIndex 这个范围
		BinaryFind(arr, middle+1, rightIndex, findVal)
	} else {
		// 找到了
		fmt.Printf("找到了，下标为%v \n", middle)
	}
}

func main() {
	arr := [6]int{1, 8, 10, 89, 1000, 1234}
	BinaryFind(&arr, 0, len(arr)-1, 1000)
}
